#include<iostream>
#include"/Users/yjc/Programming/eurekas-algorithm-path/2.Linklist/Linklist.cpp"


class Solution {
public:
    ListNode* removeNthFromEndSelf(ListNode* head, int n) {
        static int rcnt,cnt=0;
        static ListNode *vir=new ListNode(0);//虚拟头结点
        cnt++;

        if(cnt==1)
        {
            vir->next=head;
            head=vir;
        }
        if(!head->next)//边界情况
        {
            rcnt=0;
            return head->next;
        }
        ListNode *temp=removeNthFromEndSelf(head->next,n);
        rcnt++;
        if(rcnt==n)
        {
            delete(head->next);
            head->next=temp;
        }
        return head->next;
    }

    ListNode* removeNthFromEndDoublePointer(ListNode* head, int n)
    {
        ListNode vir(0);
        vir.next=head;
        ListNode *fast=&vir,*slow=&vir,*temp;
        for(int i=0;i<n;i++)
        {
            fast=fast->next;
        }
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next;
        }

        temp=slow->next->next;
        delete(slow->next);
        slow->next=temp;
        return vir.next;
    
    }
};

int main()
{
    LinkList l;
    l.insert(1,0);
    l.insert(2,0);
    l.insert(3,0);
    l.insert(4,0);
    Solution s;
    l.head=s.removeNthFromEndDoublePointer(l.head,1);
    l.print();
}